{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###   实验三  链式结构线性表的实现\n",
    "####  建立一个单链表,实现基本操作:\n",
    "    1-分别使用正位序和逆位序的方法新建一个单链表\n",
    "    2-完成插入,删除,输出的操作\n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-20T12:11:17.552903Z",
     "start_time": "2020-03-20T12:11:17.547952Z"
    },
    "cell_style": "center"
   },
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,initdata): # 节点初始化\n",
    "        self.data = initdata\n",
    "        self.next = None\n",
    "    def getData(self):   # 获得当前数据项\n",
    "        return self.data\n",
    "    def getNext(self):   # 获得后继数据项\n",
    "        return self.next\n",
    "    def setData(self,newdata):  # 设置数据项为newdata\n",
    "        self.data = newdata\n",
    "    def setNext(self,newnext):  # 设置next指针指向newnext\n",
    "        self.next = newnext\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-20T12:11:18.592349Z",
     "start_time": "2020-03-20T12:11:18.576356Z"
    },
    "cell_style": "center"
   },
   "outputs": [],
   "source": [
    "class OrderedList(Node):\n",
    "    def __init__(self): # 链表初始化\n",
    "        self.head = None\n",
    "    def add_正位序(self, item):  # 正位序添加元素的函数\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        while current != None and not stop:  # 从头遍历数据项,如果当前数据项大于加入的数据项,则停止遍历\n",
    "            if current.getData() > item:\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "        temp = Node(item)    #   停止遍历后,生成节点,并将节点插入链表中\n",
    "        if previous == None:    #  当前节点为第一个节点\n",
    "            temp.setNext(self.head)   #  设置temp的next指针指向第一个节点\n",
    "            self.head = temp   # 头节点指针指向temp节点\n",
    "        else:  # 如果当前节点不是第一个节点               \n",
    "            temp.setNext(current)    # 设置temp的next指针指向当前节点\n",
    "            previous.setNext(temp)   # 设置前驱节点的next指针指向temp\n",
    "            \n",
    "    def add_逆位序(self, item):\n",
    "        current = self.head\n",
    "        previous = None\n",
    "        stop = False\n",
    "        while current != None and not stop:\n",
    "            if current.getData() < item:   # 当前数据项小于加入的数据项,停止遍历\n",
    "                stop = True\n",
    "            else:\n",
    "                previous = current\n",
    "                current = current.getNext()\n",
    "        temp = Node(item)\n",
    "        if previous == None:\n",
    "            temp.setNext(self.head)\n",
    "            self.head = temp\n",
    "        else:\n",
    "            temp.setNext(current)\n",
    "            previous.setNext(temp)\n",
    "    \n",
    "    def print_list(self):   #  遍历并输出链表数据项\n",
    "        current = self.head\n",
    "        while current != None:\n",
    "            print(current.data, end=' ')\n",
    "            current = current.next\n",
    "        print(\"\\n\")\n",
    "\n",
    "    def showData_正位序(self):  #正位序遍历链表链表\n",
    "        print('正位序输入5个数:')\n",
    "        num = 0\n",
    "        inputList = []\n",
    "        while num<5:\n",
    "            item = int(input())\n",
    "            self.add_正位序(item)\n",
    "            num+=1\n",
    "            inputList.append(item)\n",
    "        print('正位序输入结果为:')\n",
    "        for i in inputList:\n",
    "            print(i,end = \" \")\n",
    "        print('\\n输出结果为:')\n",
    "        self.print_list()\n",
    "    \n",
    "    def showData_逆位序(self):\n",
    "        print('逆位序输入5个数:')\n",
    "        num = 0\n",
    "        inputList = []\n",
    "        while num<5:\n",
    "            item = int(input())\n",
    "            self.add_逆位序(item)\n",
    "            num+=1\n",
    "            inputList.append(item)\n",
    "        print('逆位序输入结果为:')\n",
    "        for i in inputList:\n",
    "            print(i,end = \" \")\n",
    "        print('\\n输出结果为:')\n",
    "        self.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-03-20T12:11:26.249612Z",
     "start_time": "2020-03-20T12:11:20.505788Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "正位序输入5个数:\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 4\n",
      " 5\n",
      " 5\n",
      " 3\n",
      " 2\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "正位序输入结果为:\n",
      "4 5 5 3 2 \n",
      "输出结果为:\n",
      "2 3 4 5 5 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "mylist_正位序 = OrderedList()\n",
    "mylist_正位序.showData_正位序()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "cell_style": "split"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "逆位序输入5个数:\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 5\n",
      " 8\n",
      " 3\n",
      " 9\n",
      " 4\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "逆位序输入结果为:\n",
      "5 8 3 9 4 \n",
      "输出结果为:\n",
      "9 8 5 4 3 \n",
      "\n"
     ]
    }
   ],
   "source": [
    "mylist_逆位序 = OrderedList()\n",
    "mylist_逆位序.showData_逆位序()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 实验四 链式结构线性表的实现(二)\n",
    "\n",
    "要求:\n",
    "1,实现带头节点的单链表的原地逆转(结果链表仍使用原链表的存储空间,不另开辟存储空间);\n",
    "2,用带头节点的单向链表实现集合操作AUB.(结果链表仍使用原链表的存储空间)\n",
    "     "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1-带头节点单链表逆转"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node2():\n",
    "    def __init__(self,data = None,next = None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "        \n",
    "class LinkedList():\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        \n",
    "    def creatList(self,n):\n",
    "        self.head = Node2()\n",
    "        p = self.head\n",
    "        for _ in range(n):\n",
    "            node = Node2()\n",
    "            node.data = int(input('正在建表，请输入数值：'))\n",
    "            p.next = node\n",
    "            p = p.next\n",
    "        p.next = None\n",
    "        \n",
    "    def print_list(self):   #  遍历并输出链表数据项\n",
    "        current = self.head.next\n",
    "        s = 'head'\n",
    "        while current != None:\n",
    "            s = s + '->' + str(current.data)\n",
    "            current = current.next\n",
    "        print(s)\n",
    "        \n",
    "    def reverse(self):\n",
    "        p = self.head   # p指向链表头节点\n",
    "        current = self.head.next # current指向链表第一个节点\n",
    "        p.next = None   #  令p.next为None\n",
    "        \n",
    "        #让p和current后移一位\n",
    "        temp = current.next  \n",
    "        current.next = None   \n",
    "        p = current\n",
    "        current = temp\n",
    "        while current:\n",
    "            temp = current.next\n",
    "            current.next = p\n",
    "            p = current\n",
    "            current = temp\n",
    "        \n",
    "        self.head.next = p\n",
    "        p = self.head\n",
    "        return p\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "正在建表，请输入数值： 1\n",
      "正在建表，请输入数值： 2\n",
      "正在建表，请输入数值： 3\n",
      "正在建表，请输入数值： 4\n",
      "正在建表，请输入数值： 5\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "逆转前:\n",
      "head->1->2->3->4->5\n",
      "逆转后:\n",
      "head->5->4->3->2->1\n"
     ]
    }
   ],
   "source": [
    "mylist_逆转 = LinkedList()\n",
    "mylist_逆转.creatList(5)\n",
    "print('逆转前:')\n",
    "mylist_逆转.print_list()\n",
    "mylist_逆转.reverse()\n",
    "print('逆转后:')\n",
    "mylist_逆转.print_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2,用带头节点的单向链表实现集合操作AUB"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(LinkedList_A,LinkedList_B):\n",
    "    p = LinkedList_A.head  # 初始化令p指向A链表头节点\n",
    "    current = LinkedList_A.head.next  #  初始化current指向A链表第一个节点\n",
    "    \n",
    "    while current:   # 遍历链表,直到current为None,此时P指向A链表的最后一个节点\n",
    "        temp = current.next\n",
    "        p = current\n",
    "        current = temp\n",
    "    \n",
    "    \n",
    "    p.next = LinkedList_B.head.next  # 令p的next指针指向B链表的第一个节点\n",
    "    LinkedList_B.head.next = None\n",
    "    \n",
    "\n",
    "    \n",
    "    return LinkedList_A\n",
    "\n",
    "def print_list(LinkedList):   #  遍历并输出链表数据项\n",
    "    current = LinkedList.head.next\n",
    "    s = 'head'\n",
    "    while current != None:\n",
    "        s = s + '->' + str(current.data)\n",
    "        current = current.next\n",
    "    print(s)   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "请输入mylist_A数据元素:\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "正在建表，请输入数值： 1\n",
      "正在建表，请输入数值： 2\n",
      "正在建表，请输入数值： 3\n",
      "正在建表，请输入数值： 4\n",
      "正在建表，请输入数值： 5\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "请输入mylist_B数据元素:\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "正在建表，请输入数值： 6\n",
      "正在建表，请输入数值： 7\n",
      "正在建表，请输入数值： 8\n",
      "正在建表，请输入数值： 6\n",
      "正在建表，请输入数值： 7\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "mylist_A为:\n",
      "head->1->2->3->4->5\n",
      "mylist_B为:\n",
      "head->6->7->8->6->7\n"
     ]
    }
   ],
   "source": [
    "mylist_A = LinkedList()\n",
    "print('请输入mylist_A数据元素:')\n",
    "mylist_A.creatList(5)\n",
    "mylist_B = LinkedList()\n",
    "print('请输入mylist_B数据元素:')\n",
    "mylist_B.creatList(5)\n",
    "print('mylist_A为:')\n",
    "mylist_A.print_list()\n",
    "print('mylist_B为:')\n",
    "mylist_B.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "链表AUB后的新链表为:\n",
      "head->1->2->3->4->5->6->7->8->6->7\n"
     ]
    }
   ],
   "source": [
    "print('链表AUB后的新链表为:')\n",
    "print_list(merge(mylist_A,mylist_B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "a =1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "262.747px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "position": {
    "height": "271.69px",
    "left": "1093.72px",
    "right": "20px",
    "top": "120px",
    "width": "349.992px"
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
